# -*- coding: utf-8 -*-

"""
    Time    : 2020/11/23 下午6:52
    Author  : Thinkgamer
    File    : 001-两数之和.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/two-sum/
"""

"""
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
"""


# 28 ms	13.2 MB
def twoSum1(nums, target):
	for i in range(len(nums)):
		for j in range(i + 1, len(nums)):
			if nums[i] + nums[j] == target:
				return [i, j]
	return []


# 20 ms	13.1 MB
def twoSum2(nums, target):
	hash_map = dict()
	for i, num in enumerate(nums):
		another_num = target - num
		if another_num in hash_map:
			return [i, hash_map[another_num]]
		hash_map[num] = i


# 44 ms	13.2 MB
def twoSum3(nums, target):
	# 排序后的 nums，存储的是下标
	sorted_nums = sorted(range(len(nums)), key=lambda k: nums[k])
	print(sorted_nums)
	left = 0
	right = len(nums)-1
	result = nums[sorted_nums[left]] + nums[sorted_nums[right]]
	while result != target:
		if result > target:
			right -= 1
		else:
			left += 1
		result = nums[sorted_nums[left]] + nums[sorted_nums[right]]
	return [sorted_nums[left], sorted_nums[right]]


# print(twoSum3([2, 7, 11, 15], 9))
print(twoSum3([3, 2, 4], 6))
